// https://leetcode-cn.com/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode/

class Solution {
public
  String removeDuplicateLetters(String s)
  {
    // stack:
    Stack<Character> stack = new Stack<>();

    // set: this lets us keep track of what's in our solution in O(1) time
    HashSet<Character> set = new HashSet<>();

    // map: this will let us know if there are any more instances of s[i] left in s
    HashMap<Character, Integer> map = new HashMap<>();

    // 存储 字符串中 每一个 index 对应的 char 字符
    for (int i = 0; i < s.length(); i++)
      map.put(s.charAt(i), i); // key 下标，value 字符

    for (int i = 0; i < s.length(); i++)
    {
      // 取出 index 位置上的 char 字符
      char c = s.charAt(i);

      // 使用 set 确保【唯一】性
      if (!set.contains(c))
      {
        // 栈顶 char < 当前遍历 index char &&【下标】也【小】
        // b……a……
        // - 栈顶 字符 b
        // - 当前 字符 a
        // while (!stack.isEmpty() && c < stack.peek() && i < map.get(stack.peek()))
        //   set.remove(stack.pop());

        // char 添加到 set 确保下一次无法再添加【重复】的
        set.add(c);

        // char 压栈保存
        stack.push(c);
      }
    }

    StringBuilder sb = new StringBuilder(stack.size());
    for (Character c : stack)
      sb.append(c.charValue());
    return sb.toString();
  }
}